package geek;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

/**
 * @author sam
 * 2021/10/31 22:13
 * @description
 * @editor
 * @description Pow（x,n)
 */
public class Leeson22 {

    @Test
    public void tree() {
//        Assertions.assertEquals(Math.pow(3, 4), myPow(3, 4));
        Assertions.assertEquals(Math.pow(3, 0), loopPow(3, 0));
        System.out.println(6&1);
    }

    /*
    递归  O(lgN)
     */

    private int myPow(int x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            return 1 / myPow(x, -n);
        }
        if (n % 2 == 1) {
            return x * myPow(x, n - 1);
        } else {
            return myPow(x * x, n / 2);
        }
    }


    /*
    循环
     */
    private int loopPow(int x, int n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            n = -n;
            x = 1 / x;
        }
        int result = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                result *= x;
            }
            x *= x;
            n >>= 1;
        }
        return result;
    }

}
